package Algorithm.interview;

/**
 * @Author self
 * @Date 2024/10/22 20:39
 * @Describe LCR 105. 岛屿的最大面积
 *
 * 给定一个由 0 和 1 组成的非空二维数组 grid ，用来表示海洋岛屿地图。
 *
 * 一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
 *
 * 找到给定的二维数组中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
 *
 *
 *
 * 示例 1:
 *
 *
 *
 * 输入: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
 * 输出: 6
 * 解释: 对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。
 * 示例 2:
 *
 * 输入: grid = [[0,0,0,0,0,0,0,0]]
 * 输出: 0
 *
 *
 * 提示：
 *
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 50
 * grid[i][j] is either 0 or 1
 */
/**
 * MaxAreaOfIsland 类用于解决计算岛屿的最大面积问题
 */
public class MaxAreaOfIsland {
    /**
     * 计算给定网格中岛屿的最大面积
     *
     * @param grid 二维整数数组，表示网格
     * @return 返回岛屿的最大面积
     */
    public int maxAreaOfIsland(int[][] grid) {
        // 网格的行数
        int m = grid.length;
        // 网格的列数
        int n = grid[0].length;
        // 初始化最大面积为0
        int maxArea = 0;
        // 遍历网格中的每个元素
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 当找到岛屿的一部分时
                if (grid[i][j] == 1) {
                    // 使用深度优先搜索计算当前岛屿的面积
                    int currentArea = dfs(grid, i, j);
                    // 更新最大面积
                    maxArea = Math.max(maxArea, currentArea);
                }
            }
        }
        // 返回最大面积
        return maxArea;
    }

    /**
     * 使用深度优先搜索计算岛屿的面积
     *
     * @param grid 二维整数数组，表示网格
     * @param i 当前位置的行坐标
     * @param j 当前位置的列坐标
     * @return 返回当前岛屿的面积
     */
    private int dfs(int[][] grid, int i, int j) {
        // 如果当前位置不在网格内或不是岛屿的一部分，则返回面积0
        if (!inArea(grid, i, j) || grid[i][j] != 1) {
            return 0;
        }
        // 标记当前位置已访问
        grid[i][j] = 2;
        // 初始化当前岛屿的面积为1
        int area = 1;
        // 递归计算上下左右四个方向的面积并累加
        area += dfs(grid, i - 1, j);
        area += dfs(grid, i + 1, j);
        area += dfs(grid, i, j - 1);
        area += dfs(grid, i, j + 1);
        // 返回当前岛屿的总面积
        return area;
    }

    /**
     * 检查当前位置是否在网格内
     *
     * @param grid 二维整数数组，表示网格
     * @param i 当前位置的行坐标
     * @param j 当前位置的列坐标
     * @return 如果当前位置在网格内返回true，否则返回false
     */
    private boolean inArea(int[][] grid, int i, int j) {
        // 检查当前位置是否在网格的行和列的范围内
        if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length) {
            return true;
        }
        return false;
    }

    /**
     * 主函数，用于测试计算岛屿最大面积的功能
     */
    public static void main(String[] args) {
        // 定义一个示例网格
        int[][] grid = {
                {0,0,1,0,0,0,0,1,0,0,0,0,0},
                {0,0,0,0,0,0,0,1,1,1,0,0,0},
                {0,1,1,0,1,0,0,0,0,0,0,0,0},
                {0,1,0,0,1,1,0,0,1,0,1,0,0},
                {0,1,0,0,1,1,0,0,1,1,1,0,0},
                {0,0,0,0,0,0,0,0,0,0,1,0,0},
                {0,0,0,0,0,0,0,1,1,1,0,0,0},
                {0,0,0,0,0,0,0,1,1,0,0,0,0}
        };
        // 创建 MaxAreaOfIsland 实例
        MaxAreaOfIsland maxAreaOfIsland = new MaxAreaOfIsland();
        // 计算并打印岛屿的最大面积
        int i = maxAreaOfIsland.maxAreaOfIsland(grid);
        System.out.println(i);
    }
}
